package class_slidewindows0908;
import java.util.Arrays;

public class Coding_longestSubStringWithoutRepeatingCharacters {
    /**
     * 哈希表， 字符串， 滑动窗口。
     * ///测试链接： <a href="https://leetcode.com/problems/longest-substring-without-repeating-characters/description/">...</a>
     * @param s 字符串
     * @return 返回最长子串的长度
     */
    public static int lengthOfLongestSubstring(String s){
        char[] str = s.toCharArray(); //转化为字符数组

        //7bit个数int的数组足够了
        int[] last = new int[128];
        //数组初始化为-1
        Arrays.fill(last, -1);
        int ans = 0;
        for(int l=0,r=0;r<str.length;r++){
            //处理l的边界。
            l = Math.max(l, last[str[r]]+1);
            ans = Math.max(ans, r - l + 1);
            //更新哈希表
            last[str[r]] = r;
        }
        return ans;
    }

    /**
     *
     * @param s 字符串
     * @param t 字符串
     * @return 返回s覆盖t中所有字符的最小子串
     */
        public String minWindow(String s, String t) {
            char[] str = s.toCharArray();
            char[] tar = t.toCharArray();
            //ASCII哈希表---128.
            int[] count = new int[128];

            // 记录t中每个字符的需求
            for (char ch : tar) {
                count[ch]--;
            }

            int len = Integer.MAX_VALUE; // 最小长度
            int start = 0; // 最小覆盖子串的起始位置
            int debt = tar.length; // 需要还清的字符数量

            // 滑动窗口
            for (int l = 0, r = 0; r < str.length; r++) {
                // 右指针字符进入窗口，处理还债逻辑
                if (count[str[r]] < 0) {
                    debt--; // 如果该字符是目标字符且未满足需求
                }
                count[str[r]]++; // 更新窗口中字符的数量

                // 当债务还清时，开始尝试缩小窗口
                while (debt == 0) {
                    // 如果当前窗口比之前找到的更短，则更新最小长度和起始位置
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        start = l;
                    }

                    // 移动左指针，尝试缩小窗口
                    count[str[l]]--; // 减少左边界字符
                    if (count[str[l]] < 0) {
                        debt++; // 如果移出了目标字符，增加债务
                    }
                    l++; // 移动左指针
                }
            }

            // 返回最小窗口子串
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }

}
